package done.normal_1001_1100;

import com.study.common.TreeNode;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 1026. Maximum Difference Between Node and Ancestor 节点与其祖先之间的最大差值
 * <p>
 * 给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
 * （如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
 * <p>
 * 示例：
 * 8
 * /    \
 * 3     10
 * / \     \
 * 1  6     14
 * / \    /
 * 4  7  13
 * <p>
 * 输入：[8,3,10,1,6,null,14,null,null,4,7,13]
 * 输出：7
 * 解释：我们有大量的节点与其祖先的差值，其中一些如下：
 * |8 - 3| = 5
 * |3 - 7| = 4
 * |8 - 1| = 7
 * |10 - 13| = 3
 * 在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
 **/
@SuppressWarnings("all")
public class MaximumDifferenceBetweenNodeAndAncestor {

    public int maxAncestorDiff(TreeNode root) {
        // 190527 first
        return -1;
    }

    @Test
    public void test() {
        info(maxAncestorDiff(new TreeNode(8,
                new TreeNode(3,
                        1, new TreeNode(6,
                        4, 7)), new TreeNode(10,
                null, new TreeNode(14,
                13)))));
    }
}













































/*
public int maxAncestorDiff(TreeNode root) {
    int left = diff(root.left, root.val, root.val);
    int right = diff(root.right, root.val, root.val);
    return max(left, right);
}

private int diff(TreeNode root, int max, int min) {
    if (root == null)
        return 0;

    if (root.val > max)
        max = root.val;

    if (root.val < min)
        min = root.val;

    if (root.left == null && root.right == null)
        return max - min;

    int left = diff(root.left, max, min);
    int right = diff(root.right, max, min);
    return max(left, right);
}
*/

